1. Field of the Invention
The present invention relates to a character string retrieving circuit provided within a data compressing circuit using a LZ (Lempel-Ziv) 77 method, and particularly to a character string retrieving circuit which can make character string retrieving processing become faster.
2. Description of the Related Art
A LZ77 method exists as a kind of dictionary type data compression algorithms. The LZ77 method is used in data compressing circuits within various kinds of data recording apparatus such as an ALDC (Adaptive Lossless Data Compression) within AIT format, S-AIT format or LTO format tape drive (see Cited Patent Reference 1, for example).
A data compression principle of the LZ77 method will be described. That is, a last character string of a predetermined size of character strings (data strings) that have been inputted is registered on a dictionary, a character string that is matched with a newly inputted character string (that is, character string to be compressed) is retrieved from the dictionary and the newly inputted character string is replaced with address information of the match character string. This dictionary is not a static type dictionary but it is updated so as to exclude an old character string by adding the character string just before the compressed character string in accordance with a progress of data compression. Hence, this dictionary is called a sliding dictionary.
FIG. 1 of the accompanying drawings is a schematic diagram showing an example of the manner in which a character string is retrieved from this dictionary. Although it has been customary that the dictionary is 512 bytes, 1024 bytes or 2048 bytes in size, this dictionary is 16 bytes in size for simplicity of explanation. As shown in FIG. 1, a last character string “ABCCAB . . . BCC” (each of the characters A, B, C is one byte) of 16 characters of character strings that had been inputted in the past is registered as a dictionary. The character “A” that was inputted 16 bytes before is assigned an address 0, the character “B” that was inputted 15 bytes before is assigned an address 1 and the character “C” that was inputted one byte before is assigned an address 15.
When the newly inputted character string is “ABCA”, for example, a character string of addresses 9 to 12 is matched with “ABCA”. In this case, the address 12 is outputted as a match address (address defined as the end address of the matched character string). In the end, the character string “ABCA” of 4 bytes is compressed to 2 bytes by replacing the character string “ABCA” with the leading address 9 and a match length 4.
Also, when a newly inputted character string is “ABC”, for example, a character string of addresses 0, 1, 2, a character string of addresses 4, 5, 6, a character string of addresses 9, 10, 11 and a character string of addresses 12, 13, 14 are matched with the character string “ABC”, respectively.
Further, for example, when a newly entered character string is “ABC”, a character string of addresses 0, 1, 2, a character string of addresses 4, 5, 6, a character string of addresses 9, 10, 11 and a character string of addresses 12, 13 and 14 are respectively matched with the character string “ABC”. Accordingly, in this case, 2, 6, 11 and 14 are outputted as match addresses (addresses defined as the end addresses of the match character strings).
As described above, according to the LZ77 method, data can be compressed by retrieving the character strings matched with the character string to be compressed from the dictionary. To this end, a character string retrieving circuit for carrying out this retrieving processing is provided within a data compressing circuit.
FIG. 2 is a block diagram showing an arrangement of a character string retrieving circuit provided within a data compressing circuit using the LZ77 method according to the related art.
As shown in FIG. 2, this character string retrieving circuit includes N sets of a circuit group composed of comparing circuits 51(i), two-input and one-output AND circuits 52(i), two-input and one-output multiplexers 53(i) and D flip-flop circuits 54(i) in response to respective addresses i (i=0 to N−1) of a dictionary of which size is N bytes provided within a memory (for example, a SRAM (static random-access memory)), not shown. Also, this character string retrieving circuit according to the related art includes an N-input and one-output OR circuit 55.
The respective comparing circuits 51(i) compare a character to be retrieved with characters of corresponding addresses i of a dictionary and output compared results m [i] (that is, outputs go to “1” if the character to be retrieved is matched with the character of the corresponding addresses i of the dictionary and which go to “0” if not). The resultant compared results m [i] are supplied to one input terminals of the AND circuits 52(i) of the same set and they are also supplied to input terminals S2 of the multiplexers 53(i) of the same set.
The AND circuits 52(i) are supplied at the other input terminals thereof with outputs ps [i−1] which are outputs of the D flip-flop circuits 54(i) of the sets corresponding to one address before the address of the dictionary. For example, if the AND circuits 52(i) are AND circuits 52 (N−1), then outputs ps [N−2] which are outputs from D flip-flop circuits 53 (N−2) are supplied to the other input terminals of the AND circuits 52 (N−1). Outputs ps_and_m[i] (called “match”) from the AND circuits 52(i) are supplied to the input terminals S1 of the multiplexers 53(i) of the same set and they are also supplied to the OR circuit 55.
An output orfb (that is, or feed back) from the OR circuit 55 is supplied to selection control terminals C of the multiplexers 53(i) of each set. This output orfb goes to “1” if any one match of ps_and_m [0] to ps_and_m [N−1] is “1” (if any one character string matched with the character string to be retrieved this time exists in the dictionary) and it goes to “0” if all of the outputs ps_and_m [0] to ps_and_m [N−1] are “0” (if the character string matched with the character string to be retrieved this time does not exist in the dictionary). That is, the output orfb is a match/no match signal which shows whether or not a character matched with a retrieval target character exists in the dictionary in each clock period.
The multiplexers 53(i) select the outputs ps_and_m [i] supplied to the input terminals S1 and output the outputs ps_and_m [i] from the output terminals D if the outputs orfb are “1”. If on the other hand this outputs orfb are “0”, then the multiplexers 53(i) select the outputs m [i] supplied to the input terminals S2 and output the outputs m [i] from the output terminals D. The outputs from the multiplexers 53(i) are supplied to the D input terminals of the D flip-flop circuits 54 (i) of the same set and these outputs are held at their output terminals Q until the next signal is inputted thereto. The outputs ps [i] held at the output terminals Q of the D flip-flop circuits 54(i) are supplied to the AND circuits 52(i) of the sets corresponding to one address after the address of the dictionary as outputs ps [i−1].
While FIG. 2 shows the block diagram of the character string retrieving circuit according to the related art, when this character string retrieving circuit is designed as an ASIC (Application Specified Integrated Circuit) or a programmable logic device (that is, FPGA (Field Programmable Gate Array), etc.), this character string retrieving circuit can be described as shown in FIG. 3 by using a Verilog HDL that is a kind of hardware description languages.
This character string retrieving circuit retrieves a character matched with a character of an inputted character string from a dictionary with respect to each character of the inputted character string every time (one period of operation clock) and creates the output orfb which shows whether or not a character matched with the retrieval target character exists in the dictionary. If the character matched with the retrieval target character exists in the dictionary, then the character string retrieving circuit increments the number of the characters to be retrieved one by one by using the retrieved result at the next clock period.
Specifically, if the newly entered character string is “ABCA”, for example, then this character string retrieving circuit carries out retrieval in the following procedure.
FIRST RETRIEVAL: Retrieve a character matched with the first character “A” from the dictionary;
SECOND RETRIEVAL: Retrieve a character matched with the second character “B” from the dictionary if the character matched with “A” exists in the dictionary and retrieve a character string matched with “AB” by using the preceding retrieved result of “A”;
THIRD RETRIEVAL: Retrieve a character matched with the third character “C” from the dictionary if the character string matched with “AB” exists in the dictionary and retrieve a character string matched with “ABC” by using the preceding retrieved result of “AB”; and
FOURTH RETRIEVAL: Retrieve a character matched with the fourth character “A” from the dictionary if the character string matched with “ABC” exists in the dictionary and retrieve the character string matched with “ABCA” by using the preceding retrieved result of “ABC”.
FIG. 4 is a diagram showing operations of this character string retrieving circuit with reference to an example of the case in which the character string “ABCA” is retrieved (aforementioned fourth retrieval) by using the retrieved result of the character string “ABC” in the process to retrieve the character string “ABCA” from the dictionary shown in FIG. 1.
As shown in FIG. 4, since characters at the addresses i=0, 4, 9 and 12 are matched with “A”, the compared results m [i] of the comparing circuits 51(i) of the sets corresponding to the addresses i=0, 4, 9 and 12 go to “1” and the compared results m [i] of the comparing circuits 51(i) of the sets corresponding to the remaining addresses go to “0”.
Also, in the aforementioned third retrieval (retrieval of the third character “C”), since the outputs ps [i] of the D flip-flop circuit 54(i) of the sets corresponding to the addresses i=2, 6, 11 and 14 are “1”, outputs ps [i−1] supplied to the AND circuits 52(i) of the sets corresponding to the addresses i=3, 7, 12 and 15 just one address after the addresses i=2, 6, 11 and 14 are “1” and outputs ps [i−1] supplied to the AND circuits 52(i) of the remaining sets go to “0”.
As a result, only the output ps_and_m [i] from the AND circuit 52(i) of the set corresponding to the address i=12 goes to “1” and the outputs ps_and_m [i] (match) from the AND circuits 52[i] of the remaining sets go to “0”.
Then, since one output ps_and_m [i] is “1” so that the output orfb from the OR circuit 55 goes to “1”, the ps_and_m [i] is selected by the multiplexers 53(i) and their outputs ps_and_m [ii] are held at the output terminals Q of the respective D flip-flip circuits 54(i). In this manner, the match address 12 of the character string matched with the character string “ABCA” can be obtained as earlier noted with reference to FIG. 1.
FIG. 4 shows the example in which the character string matched with the character string “ABCA” exists in the dictionary. However, unless the character string matched with the character string “ABCA” exists in the dictionary (that is, if the outputs ps_and_m [i] from the AND circuits 52(i) of all sets go to “0”), then the output orfb from the OR circuit 55 goes to “0” so that the outputs m [i] are selected by the respective D flip-flop circuits 54(i). These outputs m [i] are held at the output terminals Q of the D flip-flop circuits 54 (i). As a result, retrieval of character strings is started again from the character “A” of the address “4” by the aforementioned processing character by character.
The character string retrieving circuit shown in FIG. 2 supplies the output orfb of the OR circuit 55 to the multiplexers 53(i) of the respective sets without delay and therefore this character string retrieving circuit is called a circuit with “delay 0”.
[Cited Patent Reference 1]: Republished Patent Application of International Publication Number W02003/032296 (pages 12 to 13, FIGS. 3 and 4)
The character string retrieving circuit shown in FIG. 2 is unsuitable for making the character string retrieving processing faster due to the following reasons. That is, this character string retrieving circuit has a loop structure in which the outputs ps [i] from the D flip-flop circuits 54(i) are fed through the AND circuits 52(i) and the OR circuit 55 back to the D flip-flop circuits 54(i) and hence high-speed operation of this loop becomes the necessary condition for making the character string retrieving circuit become faster. However, the OR circuit 55 which generates the output orfb is a complex combinational circuit and it has a large delay. As a result, this loop becomes a critical path (path having the largest delay). For this reason, the maximum frequency of the operation clock is limited by this loop and therefore this character string retrieving circuit is unsuitable for making the character string retrieving processing become faster.
As a general method for increasing an operation speed of a circuit, there is known a method for realizing a pipeline processing by inserting a delay means such as a flip-flop circuit into the circuit. However, in the character string retrieving circuit shown in FIG. 2, when a flip-flop circuit is simply provided at the rear stage of the OR circuit 55 so as to delay the output orfb, it is unavoidable that “algorithm in which the retrieved result in each clock period is used in the next clock period” is changed to a different algorithm. As a result, the character string retrieving circuit becomes unable to operate as it is intended to operate.